package leetcode.year2021.month11;

// 739. 每日温度
public class _09_1DailyTemperatures739 {
  // 使用动态规划求解，建立一个dp数组，从后往前
  // 指针是可以跳跃的，不需要暴力
  public int[] dailyTemperatures(int[] temperatures) {
    int length = temperatures.length;
    int[] dps = new int[length];
    dps[length-1] = 0;
    for (int i = length-2; i >= 0; i--) {
      int point = i+1;
      while (temperatures[i] >= temperatures[point]){
        if (dps[point] == 0){
          break;
        }
        point = point + dps[point];
      }
      if (temperatures[i] >= temperatures[point] && dps[point] == 0){
        dps[i] = 0;
      } else {
        dps[i] = point - i;
      }
    }
    return dps;
  }

//  // 暴力法解决
//  public int[] dailyTemperatures(int[] temperatures) {
//    int length = temperatures.length;
//    int[] result = new int[length];
//    for (int i = 0; i < length-1; i++) {
//      int point = i+1;
//      while (point < length && temperatures[i] >= temperatures[point]){
//        point++;
//      }
//      if (point == length && temperatures[i] >= temperatures[point-1]){
//        result[i] = 0;
//        continue;
//      }
//      result[i] = point - i;
//    }
//    result[length-1] = 0;
//    return result;
//  }

  /**
   * 739. 每日温度
   * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
   *
   * 示例 1:
   *
   * 输入: temperatures = [73,74,75,71,69,72,76,73]
   * 输出: [1,1,4,2,1,1,0,0]
   * 示例 2:
   *
   * 输入: temperatures = [30,40,50,60]
   * 输出: [1,1,1,0]
   * 示例 3:
   *
   * 输入: temperatures = [30,60,90]
   * 输出: [1,1,0]
   *
   *
   * 提示：
   *
   * 1 <= temperatures.length <= 105
   * 30 <= temperatures[i] <= 100
   */
}
